package test19;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-12-01
 * Time: 15:22
 */
public class Main2 {
    public static void main(String[] args) {
        int []arr= {4,3,1,5,7,-5};
        mergeSort(arr,0,5);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if( left>=right) return;
        int mid = (left+right) /2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,mid,right);

    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int []tmp = new int[right-left+1];
        int k=0;
        while(s1<=e1 && s2<=e2){
            if( arr[s1] <= arr[s2]){
                tmp[k++]=arr[s1++];
            } else {
                tmp[k++]=arr[s2++];
            }
        }
        while(s1<=e1){
            tmp[k++]=arr[s1++];
        }
        while(s2<=e2){
            tmp[k++]=arr[s2++];
        }
        //把tmp数组更新到arr数组中
        for(int i=0;i<k;i++){
            arr[i+left]=tmp[i];
        }
    }
}
